package G.二叉搜索树;

import java.util.Stack;

public class _230_二叉搜索树中第K小的元素 {
    /**
     * 自解：牵扯到树中的大小顺序 自然就想到中序遍历---写在一个的话 返回的root数值只是返回到上一层
     * --所以单独写一个 其中添加剪枝操作
     * @param root
     * @param k
     * @return
     */
    int count=0;
    int ans =0;
    public int kthSmallest(TreeNode root, int k) {
        helper(root,k);
        return ans;

//        if (root == null){
//            return 0;
//        }
//        kthSmallest(root.left,k);
//
//        count++;
//       if(count == k){
//           re = true;
//           return root.val;
//       }
//       if (!re){
//           kthSmallest(root.right,k);
//       }
//
//       return root.val;

    }
    public void helper(TreeNode root,int k){
        if (root == null){
            return ;
        }
        kthSmallest(root.left,k);

        count++;
       if(count == k){
          ans =root.val;
       }
       //剪枝操作
       if (count>k){
           return;
       }

       kthSmallest(root.right,k);

    }

    /**
     * 迭代法 ---实际上就是中旭遍历的用栈实现
     * 循环push 弹出 root不是空 一直进左 弹出 判断--k符合 不符合 root= right进去
     */
    public int kthSmallest1(TreeNode root, int k) {

        Stack<TreeNode> stack = new Stack<>();

        while (true){

            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root= stack.pop();
            if (--k==0){
                return root.val;
            }
            root = root.right;


        }



    }

}
